package com.yiwenup.leetcode.top_interview_150;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 文件描述
 *
 * @Project struct-algorithm
 * @Package com.yiwenup.leetcode.top_interview_150
 * @Author yiwenup
 * @Date 2024-12-11 21:23:53
 * @Description https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150
 */
public class No0030 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();

        Arrays.sort(words);
        int step = words[0].length();
        int space = words.length * step;
        int left = 0;
        String[] temp = new String[words.length];
        for (int right = space; right <= s.length(); right++) {
            String sub = s.substring(left, right);
            int idx = 0;
            for (int i = 0; i < temp.length; i++) {
                temp[i] = sub.substring(idx, idx + step);
                idx += step;
            }
            Arrays.sort(temp);
            if (Arrays.equals(words, temp)) {
                ans.add(left);
            }
            left++;
        }

        return ans;
    }
}
